package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/insertion-sort-list/
 * @create 2025/9/11 21:28
 * @since JDK17
 */

public class Solution17 {
    public ListNode insertionSortList(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode(0, head), p = head, next;
        ListNode q, pre, last;
        while (p != null) {
            next = p.next;  // 找到下一个
            int t = p.val;
            for (pre = newHead, q = pre.next; q != p; pre = q, q = q.next) {
                if (t < q.val) {
                    break;
                }
            }
            if (q != p) {   // 有较小值
                for (last = q; last.next != p; last = last.next);   // 找到p的前一个
                pre.next = p;
                p.next = q;
                last.next = next;
            }

            p = next;
        }

        return newHead.next;
    }
}
